package mashibing.class18;

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
 * 玩家A和玩家B依次拿走每张纸牌
 * 规定玩家A先拿，玩家B后拿
 * 但是每个玩家每次只能拿走最左或最右的纸牌
 * 玩家A和玩家B都绝顶聪明
 * 请返回最后获胜者的分数。
 */
public class Class18_2_CardsInLine {

    /**
     * 方法1：根据规则，返回获胜者的分数
     */
    private static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int first = f1(arr, 0, arr.length - 1);
        int second = g1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }

    // arr[L..R]，先手获得的最好分数返回
    private static int f1(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        int p1 = arr[l] + g1(arr, l + 1, r);
        int p2 = arr[r] + g1(arr, l, r - 1);
        return Math.max(p1, p2);
    }

    // arr[L..R]，后手获得的最好分数返回
    private static int g1(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        // 对手拿走了L位置的数
        int p1 = f1(arr, l + 1, r);
        // 对手拿走了R位置的数
        int p2 = f1(arr, l, r - 1);
        return Math.min(p1, p2);
    }

    /**
     * 方法2
     */
    private static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[][] fmap = new int[n][n];
        int[][] gmap = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int second = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }

    // arr[L..R]，先手获得的最好分数返回
    private static int f2(int[] arr, int l, int r, int[][] fmap, int[][] gmap) {
        if (fmap[l][r] != -1) {
            return fmap[l][r];
        }
        int ans;
        if (l == r) {
            ans = arr[l];
        } else {
            int p1 = arr[l] + g2(arr, l + 1, r, fmap, gmap);
            int p2 = arr[r] + g2(arr, l, r - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[l][r] = ans;
        return ans;
    }

    // arr[L..R]，后手获得的最好分数返回
    private static int g2(int[] arr, int l, int r, int[][] fmap, int[][] gmap) {
        if (gmap[l][r] != -1) {
            return gmap[l][r];
        }
        int ans;
        if (l == r) {
            ans = 0;
        } else {
            // 对手拿走了L位置的数
            int p1 = f2(arr, l + 1, r, fmap, gmap);
            // 对手拿走了R位置的数
            int p2 = f2(arr, l, r - 1, fmap, gmap);
            ans = Math.min(p1, p2);
        }
        gmap[l][r] = ans;
        return ans;
    }

    /**
     * 方法3
     */
    private static int win3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[][] fmap = new int[n][n];
        int[][] gmap = new int[n][n];
        for (int i = 0; i < arr.length; i++) {
            fmap[i][i] = arr[i];
        }
        // 遍历对角线
        for (int i = 1; i < n; i++) {
            int row = 0;
            int col = i;
            while (col < n) {
                fmap[row][col] = Math.max(arr[row] + gmap[row + 1][col], arr[col] + gmap[row][col - 1]);
                gmap[row][col] = Math.min(fmap[row + 1][col], fmap[row][col - 1]);
                row++;
                col++;
            }
        }
        return Math.max(fmap[0][n - 1], gmap[0][n - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));
    }

}
